#include <stdio.h>
#include <stdlib.h>

// 邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 邻接表
typedef struct AdjList {
    AdjListNode *head;  // 链表的头指针
} AdjList;

// 图的结构，包括顶点数和邻接表数组
typedef struct Graph {
    int numVertices;
    AdjList* array;
} Graph;

// 创建新节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->array = (AdjList*) malloc(numVertices * sizeof(AdjList));
    
    for (int i = 0; i < numVertices; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加边到有向图
void addEdge(Graph* graph, int src, int dest) {
    // 添加边从src到dest (有向)
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    // 注意：不像无向图，我们不需要添加从dest到src的边
}

// 打印图的邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->numVertices; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

void printOutDegrees(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        int count = 0;
        for (AdjListNode* p = graph->array[i].head; p != NULL; p = p->next) {
            count++;
        }
        printf("Out-degree of vertex %d is %d\n", i, count);
    }
}
void printInDegrees(Graph* graph) {
    int inDegrees[graph->numVertices];
    for (int i = 0; i < graph->numVertices; i++) {
        inDegrees[i] = 0; // 初始化入度数组
    }

    for (int i = 0; i < graph->numVertices; i++) {
        for (AdjListNode* node = graph->array[i].head; node != NULL; node = node->next) {
            inDegrees[node->dest]++; // 对于每个节点，增加其目的顶点的入度
        }
    }

    for (int i = 0; i < graph->numVertices; i++) {
        printf("In-degree of vertex %d is %d\n", i, inDegrees[i]);
    }
}
int main() {
    int numVertices = 4;
    Graph* graph = createGraph(numVertices);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printGraph(graph);
    printOutDegrees(graph);
    printInDegrees(graph);
    return 0;
}
